package com.hl.algor_data_struct.dac;

/**
 * Created by yuanhailong on 2021/10/27.
 * 利用分治算法解决汉诺达问题
 */
public class Hanoitoer {
    private static int loop=0;
    public static void main(String[] args) {
        hanoitoer(5,'A','B','C');
        System.out.println("移动次数:"+loop);
    }


    /**
     *
     * @param num  一共有一个盘
     * @param a    a塔
     * @param b    b塔
     * @param c    c塔
     */
    public static void hanoitoer(int num,char a,char b,char c){

        loop++;

        //如果只有一个盘，则直接将A-> C
        if(num==1){
            System.out.println("第1个盘从 "+ a+"->"+c);
        }else{
            //只要num>=2则将最下面一个盘当做一个整体，上面所有的盘当做一个整体
            //即将最下面的盘当做一个盘，上面所有的盘当做一个盘处理

            //1 先把最上面的所有盘需要移动到B
            hanoitoer(num-1,a,c,b);
            //2 把最下面的盘移动到c  A-C
            System.out.println("第"+num+"个盘从 "+ a+"->"+c);
            //3 把B搭上面所有的盘移动搭C
            hanoitoer(num-1,b,a,c);
        }
    }
}
